public class Solution72 {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        if ( m*n == 0) {
            return m+n;
        }

        int[][] dp = new int[m+1][n+1];

        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }

        for (int j = 1; j <= m; j++) {
            dp[j][0] = j;
            for (int i = 1; i <= n; i++) {

                dp[j][i] = Math.min(dp[j][i-1], dp[j-1][i]);
                
                if (word1.charAt(j-1) != word2.charAt(i-1)){
                    dp[j][i] = Math.min(dp[j][i], dp[j-1][i-1]);
                } else {
                    dp[j][i] = Math.min(dp[j][i], dp[j-1][i-1]-1);
                }
                dp[j][i]++;
            }
        }
        return dp[m][n];
    }
}
